LeetCode 第 188 题：买卖股票的最佳时机 IV（动态规划） |
您所在的位置：网站首页 › 股票最大收益 动态规划 › LeetCode 第 188 题：买卖股票的最佳时机 IV（动态规划） |
|
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv 第 1 步：状态定义 dp[i][j][K] ：表示到第 i 天为止，已经交易了 j 次，并且当前持股状态为 K 的最大收益 说明： 到第 i 天为止（从 0 开始计算，到 len - 1 ），考虑的区间是 [0, i]，这里 len 为数组 prices 的长度；已经交易了 j 次，j 从 0 开始计算，到 k - 1 为止；持股状态 K （大写）只有 2 个值：0 和 1 。0 表示不持股，1 表示持股，为了与 k 区分，因此使用 K（大写）。第 2 步：状态转移方程 下面考虑 dp[i][j][0] 和 dp[i][j][1] 可以怎样转移过来。 动态规划用于解决多阶段的决策问题，这里的阶段就是每一天，因此，状态都是从前一天的某一个之前的状态转移过来。 dp[i][j][0]：表示这一天发生了第 j 次交易，并且不持股。特别说明一下：发生交易的标志是在某一天，发生一次购买股票的行为，即发生一次交易。 分类讨论的依据是：昨天是否持股。 （1）昨天不持股，今天还不持股，说明没有发生新的交易； （2）昨天持股，今天不持股，说明这次交易结束了。这两种情况都在一次交易里。 二者取最大值，即： dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])注意：中间的那个表示交易次数的状态都是 j。 dp[i][j][1]：表示这一天已经交易了 j 次，并且持股。分类讨论的依据依然是：昨天是否持股。 （1）昨天持股，今天还持股，说明没有发生新的交易，这两天在同一个交易区间里； （2）昨天不持股，今天持股，说明开启了一次新的交易。 二者取最大值，即： dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])第 3 步： 初始化 所有持股的状态值都设置为一个很大的负数（至少应该是最大的股价的负数 - 1），表示未知，不持股的时候，状态值为 0；这里 i 和 j 下标都有 -1 ，所以 i 和 j 可以多设置一行，以避免复杂的分类讨论。以下只展示不多设置一行的代码。多设置一行的代码留给读者完成。第 4 步：输出 最后一个阶段的最后一个状态，且是不持股的那个状态，即 dp[len - 1][k - 1][0]（i 和 j 不多设置一行的时候）。 第 5 步：考虑状态压缩 注意到两个状态转移方程，当前行只依赖上一行，并且 j 只依赖 j - 1，但是是另一张表的状态值，因此直接砍掉第一维即可。 先写出没有考虑状态压缩的版本。 Java 代码： public class Solution { public int maxProfit(int k, int[] prices) { int len = prices.length; // 特判 if (k == 0 || len = len / 2) { return greedy(prices, len); } // dp[i][j][K]：到下标为 i 的天数为止（从 0 开始），到下标为 j 的交易次数（从 0 开始） // 状态为 K 的最大利润，K = 0 表示不持股，K = 1 表示持股 int[][][] dp = new int[len][k][2]; // 初始化：把持股的部分都设置为一个较大的负值 for (int i = 0; i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |